package base.sort;

import java.util.Arrays;

/**
 * 描述：
 *     快速排序，用荷兰国旗问题优化
 *
 *     想绕开原始的样本状况，可以通过以下两种方法：
 *     1）随机
 *     2）hash打乱
 *
 *     随机快排避免了特殊样本增加的时间复杂度（比如有序的，每次选最后一个数，会退化成O(N^2)）
 *     用随机选取划分点作为标准，将原来由样本量决定的时间复杂度，变成概念事件，长期期望的时间复杂度为O(N * logN)
 *     空间复杂读，也是一个概念，长期期望是O(logN)，最差是O(N)（有序），空间都用在记录划分点
 *     强烈推荐使用
 * @author hl
 * @version 1.0
 * @date 2020/10/24 10:07
 */
public class Code_06_QuickSort {
    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -7, 11, 9, 6, 8};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr){
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            swap(arr, (int) (l + (Math.random() * (r - l + 1))), r);//随机快排（随机选一个数进行）
            int[] p = partition(arr, l, r);
            quickSort(arr,l,p[0] - 1);
            quickSort(arr,p[1] + 1,r);
        }
    }

    private static int[] partition(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r;
        while(l < more){
            if (arr[l] < arr[r]) {
                swap(arr, ++less, l++);
            }else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            }else{
                l++;
            }
        }
        swap(arr, more, r);
        return new int[] {less+1, more};//返回中间值的边界
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
